package hashtable.isangram;

/**题目:
 * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
   示例 1:
   输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
   输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 *
 * 思路：哈希表 + 排序
 * 具体步骤：
 *    - 创建一个哈希表，键是排序后的字符串，值是原始字符串组成的列表。
 *    - 遍历字符串数组，对每个字符串进行排序，然后将排序后的字符串作为键，将原始字符串添加到该键对应的列表中。
 *    - 最后，将哈希表中的所有值（即列表）汇总到一个大列表中返回。
 */

import java.util.*;

/**
 * 知识点:
   1.将char的数组变为string
     new String(char[] value) 是 String 类的构造函数
     它会将字符数组的内容复制到一个新的字符串对象中
     示例：new String(new char[]{'a','e','t'}) → "aet"

   2.对字符数组进行升序排序:Arrays.sort(数组名);
 */

//问题核心是将具有相同字母组成的字符串分组
//HashMap 的键值对结构天然适合"分组归类"场景
public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 创建哈希表：键是排序后的字符串，值是原始字符串列表
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            // 将字符串转换为字符数组并排序
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sorted = new String(chars);  // 排序后的字符串作为键

            // 如果键不存在则创建新列表
            if (!map.containsKey(sorted)) {
                map.put(sorted, new ArrayList<>());
            }

            // 将原始字符串添加到对应列表中
            map.get(sorted).add(str);
        }

        // 返回所有分组（哈希表的值集合）
        return new ArrayList<>(map.values());
    }
}
